package q35_searchInsert;

public class Solution_1 {
    public static void main(String[] args) {
        System.out.println(searchInsert(new int[]{1,2,3,3,4,5},4));
    }
    public static int searchInsert(int[] nums, int target) {
        if (target <= nums[0]){
            return 0;
        }
        if (target >= nums[nums.length - 1]){
            return nums.length;
        }
        int p1,p2;
        // 左右指针设置
        if(target > nums[(nums.length - 1)/2]){
            p1 = (nums.length - 1)/2;
            p2 = nums.length - 1;
        }else if (target < nums[(nums.length - 1) / 2]){
            p1 = 0;
            p2 = (nums.length - 1)/2;
        }else{
            return (nums.length - 1)/2;
        }

        while(p2 - p1 > 1){
            if (target > nums[(p1 + p2)/2]) {
                p1 = (p1 + p2)/2;
            }else if(target < nums[(p1 + p2)/2]){
                p2 = (p1 + p2)/2;
            }else{
                return (p1 + p2)/2;
            }
        }

        return p1 + 1;

    }
}
